The present invention relates generally to integrated circuit memory devices and, more particularly, to a content addressable memory capable of detecting and correcting bit errors contained therein when used in conjunction with error checking and correction techniques.
A content addressable memory (CAM) is a storage device in which storage locations are identified by their contents, not by names or positions. A search argument is presented to the CAM and the location that matches the argument asserts a corresponding match line. One use for such a memory is in dynamically translating logical addresses to physical addresses in a virtual memory system. In this case, the logical address is the search argument and the physical address is produced as a result of the dynamic match line selecting the physical address from a storage location in a random access memory (RAM). CAMs are also frequently used for Internet address searching.
A CAM typically includes an array of CAM cells, where each row of the CAM array corresponds to a stored word. The CAM cells in a given row couple to a word line and a match line associated with the row. The word line connects to a control circuit that can either select the row for a read/write operation or bias the word line for a search. The match line carries a signal that, during a search, indicates whether the word stored in the row matches an applied input value. Each column of the conventional CAM array corresponds to the same bit position in all of the CAM words, while the CAM cells in a particular column are coupled to a pair of bit lines associated with the column. A search is applied to each pair of bit lines, which have a pair of complementary binary signals thereon that represent a bit of an input value. Each CAM cell changes the voltage on the associated match line if the CAM cell stores a bit that does not match the bit represented on the attached bit lines. Accordingly, if the voltage on a match line remains unchanged during a search, the word stored in that row of CAM cells matches the input word.
In conventional CAM systems, a detected mismatch condition is accepted as accurate, regardless of whether the mismatch results from an actual data mismatch or from a flipped cell(s) caused by a soft error. A soft error may occur as a result of phenomena such as impacts of cosmic rays or alpha particles, wherein the value of a binary bit of stored data is changed. Currently, some CAM arrays are designed to be refreshed periodically in order to fix any flipped cells. However, in so doing, a risk is taken in the meantime that some mismatches might actually be false mismatches.
Error checking and correction (ECC) algorithms have been used to address the problem of soft error. The most simple ECC algorithms provide the ability to correct a single bit error and detect a double bit error by reading and writing the original data along with a checksum data word. More complicated algorithms may correct more than a single bit errors and detect more than double bit errors by utilizing more checksum data bits. The data, along with the checksum, may be tested for validity and potentially corrected or otherwise marked as xe2x80x9cuncorrectably corruptxe2x80x9d. A significant characteristic of ECC encoded data is that no two combinations of data and checksum are two bits or less different.
It is desirable to be able to conduct CAM searches that recognize a single bit mismatch as a complete match. When such a CAM search is performed in conjunction with error checking and correction techniques, a one bit mismatch would be deemed xe2x80x9ccorrectably corruptxe2x80x9d and thus attributed to soft error as opposed to a true one bit data mismatch. Existing CAM configurations, however, are not presently adapted to make this distinction.
The above discussed and other drawbacks and deficiencies of the prior art are overcome or alleviated by a content addressable memory (CAM) and method capable of detecting and correcting bit errors contained therein. In an exemplary embodiment, the CAM includes a plurality of individual CAM cells for storing a codeword having a number of bits associated therewith. A match line is coupled to each of the plurality of individual CAM cells, and is used to indicate a match status of a comparand word that is compared to the stored codeword. The match status is reflective of either a match state or a mismatch state. The CAM is designed to store a word of M plus N bits, wherein M is the number of bits in the data and N is the number of bits in the ECC checksum code. A sensing apparatus is used for latching the match line to the match state whenever the comparand word mismatches the stored codeword by a number of N or fewer bits.
In a preferred embodiment, the sensing apparatus also latches the match line to the mismatch state whenever the comparand word mismatches the stored codeword by more than N bits. The sensing apparatus further includes a reference match line which is discharged at a selected rate from a precharged state during a compare operation. During a compare operation, the sensing apparatus determines the match status by comparing the selected rate of discharge of the reference match line to a rate of discharge of the match line. If the selected rate of discharge of the reference match line is greater than the rate of discharge of the match line, then the match line is latched to the match state. However, if the rate of discharge of the match line is greater than the selected rate of discharge of the reference match line, then the match line is latched to the mismatch state.
In an alternative embodiment, the CAM cells are further adapted to correct any mismatching bits stored therein if the match line is latched to said match state. Each of the CAM cells further include a pair of cross coupled inverters configured as a data storage latch. A first access transistor selectively couples a bit line to a first node within the data storage latch, and a second access transistor selectively couples a complementary bit line to a second node within the data storage latch. The first node has a voltage value representing the value of the bit stored in the data storage latch, while the second node has a voltage value representing the complementary value of the bit stored in the data storage latch. A third access transistor selectively couples the first node to said match line, and a fourth access transistor selectively couples the second node to the match line.
If a comparand bit applied to a given CAM cell does not match a stored bit within the CAM cell, and if the match line is also latched to said match state, then the stored bit within the CAM cell is caused to be inverted. However, a matching stored bit within the CAM cell is prevented from being inverted by the match line if the match line is latched to the mismatch state.